package leetcode


//https://leetcode.com/problems/4sum/
/**
 *
Given an sort.getArray nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the sort.getArray which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given sort.getArray nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1,  0, 0, 1],
[-2, -1, 1, 2],
[-2,  0, 0, 2]
]
 */

fun main(args: Array<String>) {

    println(fourSum(intArrayOf(1, 0, -1, 0, -2, 2), 0))
    //-2,-1,0,0,1,2
}

fun fourSum(nums: IntArray, target: Int): List<List<Int>> {

    val result = arrayListOf<List<Int>>()
    if (nums.size < 4) return result

    nums.sort()

    var i = 0

    while (i <= nums.size - 4) {
        var j = i + 1

        //内层循环即3sum 的解法
        while (j <= nums.size - 3) {
            val restSum = target - nums[i] - nums[j]

            var left = j + 1
            var right = nums.size - 1

            while (left < right) {
                val leftValue = nums[left]
                val rightValue = nums[right]
                val sum = leftValue + rightValue
                when {
                    sum > restSum -> {
                        while (left < right && nums[right] == rightValue) right--
                    }
                    sum == restSum -> {
                        result.add(listOf(nums[i], nums[j], leftValue, rightValue))
                        while (left < right && nums[right] == rightValue) right--
                        while (left < right && nums[left] == leftValue) left++
                    }
                    else -> while (left < right && nums[left] == leftValue) left++
                }
            }

            val jValue = nums[j]
            while (j <= nums.size - 3 && nums[j] == jValue)
                j++
        }

        val iValue = nums[i]
        while (i <= nums.size - 4 && nums[i] == iValue)
            i++
    }
    return result
}